#include "contourtree.h"
#include "contreeconstructor.h"
#include "disjointset.h"
#include "augmentedctree.h"

using namespace PBVP;

const int ConTreeConstructor::MAX_NEI_NUM = 14;

ConTreeConstructor::ConTreeConstructor()
{
	m_pCPVector = NULL;
}

ConTreeConstructor:: ~ConTreeConstructor(void) 
{
    if (m_pCPVector) delete m_pCPVector;
}

ContourTree* ConTreeConstructor::getContourTree() {
	calcSortedCriticalPoints();
#ifdef DEBUG_CONTREE
	printf("start constructing join tree ... \n");
#endif
    ContourTree* joinTree = constructJoinTree();
#ifdef DEBUG_CONTREE
	printf("start constructing split tree ...\n");
#endif
    ContourTree* splitTree = constructSplitTree();

    ContourTree* conTree = ContourTree::mergeTree(joinTree, splitTree);
    delete joinTree;
    delete splitTree;
    return conTree;
}

AugmentedContourTree* ConTreeConstructor::getAugmentedContourTree()
{
	ContourTree *conTree = getContourTree();
	AugmentedContourTree *augTree = new AugmentedContourTree(conTree);
	delete conTree;
	return augTree;
}

/// Add every vertex as a critical point in a sorted order
void ConTreeConstructor::calcSortedCriticalPoints()
{
	// The critical point vector is already available. Just return
	if (m_pCPVector != NULL) return;
	
	m_pCPVector = new std::vector<CriticalPoint>;
	int nCP = getNumOfCPs();
	for (int id = 0; id < nCP; id ++)
	{
		CriticalPoint cp(id, getCPValue(id));
		m_pCPVector->push_back(cp);
	}
	std::sort(m_pCPVector->begin(), m_pCPVector->end());
	calcLUStars();
}

ContourTree* ConTreeConstructor::constructJoinTree(void)
{
    ContourTree* joinTree = new ContourTree();
    int i, nv = getNumOfCPs();

	assert(m_pCPVector);

    int *map = new int[nv];
    for (i = 0; i < nv; i++) {
        map[(*m_pCPVector)[i].id] = i;
    }

	printf("construct join tree using DisjointSet ...\n");
    DisjointSet* djs = new DisjointSet(nv);
	std::vector<CriticalPoint>::iterator it;
    for (it = m_pCPVector->begin(); it != m_pCPVector->end(); ++it) {
        int id = (*it).id;
        joinTree->addNode(*it);
        if (isMinimum(*it)) {
            djs->makeSet(map[id]);
            continue;
        }
        // (*it) is not a minimum point. Each vertex has 14 neighboring vertices
        int nNeighbors, neighbors[MAX_NEI_NUM];
        nNeighbors = getNeighbors(id, neighbors); 
        for (int j = 0; j < nNeighbors; j++) {
            int nid = neighbors[j];
            if (map[nid] < map[id]) {
                int mid, pj;
                int pi = djs->find(map[id]);
                mid = pj = djs->find(map[nid]);
                if (pi == pj) continue;
                if (pi == -1) djs->addElement(map[id], pj);
                else mid = djs->link(pi, pj);
                int k = (*m_pCPVector)[djs->getMaxNode(pj)].id;
#ifdef _DEBUG
                //printf("add arc (%d %d)\n", id, k);
#endif			
                joinTree->addArc(id, k, nid);
                djs->setMaxNode(map[id], mid);
            }
        }
    }

    delete djs;
    delete[] map;

    // joinTree->setMaxID(getNumOfCPs());
	joinTree->setMaxID((*m_pCPVector)[nv-1].id);
    return joinTree;
}

ContourTree* ConTreeConstructor::constructSplitTree(void)
{
    ContourTree* p_tree = new ContourTree();
    int i, nv = getNumOfCPs();

	assert(m_pCPVector);

    int *p_map = new int[nv];
    for (i = 0; i < nv; i++) {
        p_map[(*m_pCPVector)[i].id] = nv - 1 - i;
    }

    DisjointSet djs(nv);
	std::vector<CriticalPoint>::reverse_iterator rit;
    for (rit = m_pCPVector->rbegin(); rit != m_pCPVector->rend(); ++rit) {
        int id = (*rit).id;
        p_tree->addNode(*rit);
        if (isMaximum(*rit)) {
            djs.makeSet(p_map[id]);
            continue;
        }

        int nNeighbors, neighbors[MAX_NEI_NUM];
        nNeighbors = getNeighbors(id, neighbors); 
        for (int j = 0; j < nNeighbors; j++) {
            int nid = neighbors[j];
            if (p_map[nid] < p_map[id]) {
                int mid, pj;
                int pi = djs.find(p_map[id]);
                mid = pj = djs.find(p_map[nid]);
                if (pi == pj) continue;
                if (pi == -1) djs.addElement(p_map[id], pj);
                else mid = djs.link(pi, pj);
                int k = (*m_pCPVector)[nv-1-djs.getMaxNode(pj)].id;
#ifdef _DEBUG
                //printf("add arc (%d %d)\n", id, k);
#endif
                p_tree->addArc(id, k, nid);
                djs.setMaxNode(p_map[id], mid);
            }
        }
    }
    delete[] p_map;

    //p_tree->setMaxID(getNumOfCPs());
	p_tree->setMaxID((*m_pCPVector)[0].id);
    return p_tree;
}